package algorithmExample.tree;

import lombok.val;

/**
 * @Author: zhangrongqing
 * @Date: 2019/11/20 11:16
 */
//题目:https://leetcode-cn.com/problems/validate-binary-search-tree/
public class ValidateBinarySearchTree {
    public boolean isValidBST(TreeNode root) {
        boolean rightValue = true, leftValue = true;
        if (root.left != null) {
            rightValue = root.left.val < root.val && isValidLeft(root.left, root.val);
        }
        if (root.right != null) {
            leftValue = root.right.val > root.val && isValidRight(root.right, root.val);
        }
        return rightValue && leftValue;
    }

    public boolean isValidLeft(TreeNode node, Integer rootValue) {
        boolean rightValue = true, leftValue = true;
        if (node == null) {
            return true;
        }
        if (node.left != null) {
            leftValue = node.left.val < rootValue && node.left.val < node.val && isValidLeft(node.left, rootValue);
        }
        if (node.right != null) {
            rightValue = node.right.val < rootValue && node.right.val > node.val && isValidLeft(node.right, rootValue);
        }
        return rightValue && leftValue;
    }

    public boolean isValidRight(TreeNode node, Integer rootValue) {
        boolean rightValue = true, leftValue = true;
        if (node == null) {
            return true;
        }
        if (node.left != null) {
            leftValue = node.left.val > rootValue && node.left.val < node.val && isValidRight(node.left, rootValue);
        }
        if (node.right != null) {
            rightValue = node.right.val > rootValue && node.right.val > node.val && isValidRight(node.right, rootValue);
        }
        return rightValue && leftValue;
    }

    public static void main(String[] args) {
        Integer[] input = new Integer[]{10, 5, 15, null, null, 6, 20};
        TreeNode root = TreeUtil.toTree(input);
        boolean result = new ValidateBinarySearchTree().isValidBST(root);
        System.out.println(result);
    }
}
